#include "CMaxHeap.h"
#include "CIndexMaxHeap.h"
#include <iostream>

template<typename T>
void heapSort1(T arr[], int n){

    MaxHeap<T> maxheap = MaxHeap<T>(n);
    for (int i=0; i<n; i++)
        maxheap.insert(arr[i]);
    //cout <<maxheap.size()<<endl;
    for (int i=n-1; i>=0; i--)
        arr[i] = maxheap.extractMax();
}

template<typename T>
void heapSort2(T arr[], int n){

    MaxHeap<T> maxheap = MaxHeap<T>(arr, n);
    for (int i=n-1; i>=0; i--)
        arr[i] = maxheap.extractMax();
}


template<typename T>
void __shiftDown(T arr[], int n, int k){

    T e = arr[k];
    while( 2*k+1 < n ){
        int j = 2*k+1;
        if( j+1 < n && arr[j+1] > arr[j] )
            j += 1;

        if( e >= arr[j] ) break;


        arr[k] = arr[j];
        k = j;
    }

    arr[k] = e;
    }

template<typename T>
void heapSort(T arr[], int n){
    //heapify
    for(int i=(n-1-1)/2; i>=0; i--)
        __shiftDown(arr, n, i);
    for(int i=n-1; i>0; i--){
        swap(arr[0], arr[i]);
        __shiftDown(arr, i, 0);
    }
}


template<typename T>
void heapSortUsingIndexMaxHeap(T arr[], int n){

    IndexMaxHeap<T> indexMaxHeap = IndexMaxHeap<T>(n);
    for( int i = 0 ; i < n ; i ++ )
        indexMaxHeap.insert( i , arr[i] );
    assert( indexMaxHeap.testReverseIndex() );

    for( int i = n-1 ; i >= 0 ; i -- )
        arr[i] = indexMaxHeap.extractMax();
}
